package com.xxy.sort;

import com.sun.deploy.uitoolkit.impl.awt.AWTDragHelper;

import java.lang.reflect.Array;
import java.util.Arrays;

/**
 * @author xxy
 * @create 2020 11 20 20:04
 * 插入排序
 * 把n个带排序的元素，看成为一个有序列表，和无序列表
 * 开始时，有序列表只包含一个元素，排序过程中，每次从无序表中取一个数
 * ，把它与有序列表的排序码进行比较，将他查到适当的位置，使之成为有序列表。
 *
 */
public class InsertSort {
    public static void main(String[] args) {
        int[] arr = {4,3,2,1};
        insetSort(arr);
        System.out.println(Arrays.toString(arr));
    }
    public static void insetSort(int[] arr){
        for(int i=1;i<arr.length;i++){
            int insertVal = arr[i];
            int insertIndex = i-1;
            while (insertIndex>=0&&insertVal<arr[insertIndex]){
                arr[insertIndex+1] =arr[insertIndex];
                insertIndex--;
            }
            arr[insertIndex+1]=insertVal;
        }
    }
}
